package oct2013;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Yinzi Chen
 * @date Nov 5, 2013
 */
public class Triangle {

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[2][n + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][1] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            int p = (i + 1) % 2, c = i % 2;
            Arrays.fill(dp[c], Integer.MAX_VALUE);
            for (int j = 1; j <= i + 1; ++j) {
                dp[c][j] = Math.min(dp[p][j], dp[p][j - 1])
                        + triangle.get(i).get(j - 1);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            min = Math.min(min, dp[(n + 1) % 2][i]);
        }
        return min;
    }
}
